
# 描述
# 给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组
#
# 注意：
# 1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B
# 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n
# 2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，
# 且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印
# 3. A 数组在[0,m-1]的范围也是有序的

# 示例1
# 输入：
# [4,5,6],[1,2,3]
# 返回值：
# [1,2,3,4,5,6]
# 说明：
# A数组为[4,5,6]，B数组为[1,2,3]，后台程序会预先将A扩容为[4,5,6,0,0,0]，
# B还是为[1,2,3]，m=3，n=3，传入到函数merge里面，
# 然后请同学完成merge函数，将B的数据合并A里面，最后后台程序输出A数组

class Solution:
    def merge(self , A, m, B, n):
        # write code here
        i = m - 1
        j = n - 1
        p = m + n - 1  # i,j指针指向原末尾，p指针指向合并后的A末尾
        while i >= 0 and j >= 0:  # 合并A、B数组， 比较i,j指针指向的元素，将大的那个丢进去
            if A[i] > B[j]:
                A[p] = A[i]
                p -= 1
                i -= 1
            else:
                A[p] = B[j]
                p -= 1
                j -= 1
        while j >= 0:  # 如果B数组还有剩余，则直接全部移到A数组中
            A[p] = B[j]
            p -= 1
            j -= 1